package com.xy6.algo.sort;

import java.util.Arrays;

/**
 * 插入排序
 * <pre>
 * 时间复杂度：O(n^2)，空间复杂度：O(n+1)
 * 
 * 遍历数组元素1-(n-1)，当前索引i
 * i为1时，遍历有序序列[0]中元素
 * 从后向前遍历，当前索引j
 * 比较i、j两个元素大小，如果j元素比i元素大，则将j+1元素赋值为j元素，实现元素后移。
 * 否则j+1元素赋值为i元素，遍历终止。有序序列增加一个元素
 * i为2时，遍历有序序列[0,1]中元素，重复上述步骤。
 * i为3时，遍历有序序列[0,1,2]中元素，重复上述步骤。
 * 遍历直至i为n-1，遍历终止。数组元素已按从小到大排列。
 * 
 * 原地排序，需要常数个存储空间。
 * </pre>
 * 
 * @author frank
 * @since 2017-06-02
 */
public class SortInsert {

	/**
	 * 输出结果：
	 * 
	 * 1: 1 3 2
	 * 2: 1 2 3
	 */
	public static void main(String[] args) {
		int[] arr = new int[]{
				3, 1, 2, 5, 6, 4
		};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
	/**
	 * 插入排序
	 * 
	 * @param arr
	 */
	public static void sort(int[] arr){
		int size = arr.length;
		int temp = 0;
		for (int i = 1; i < size; i++) {
			temp = arr[i];
			int j = 0;
			for (j = i - 1; j >= 0; j--) {
				if(arr[j] > temp){
					arr[j + 1] = arr[j];
				} else {
					break;
				}
			}
			arr[j + 1] = temp;
		}
	}

}
